package leetcode.editor.cn;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * [870]优势洗牌
 * advantage-shuffle
 */
//给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。 
//
// 返回 A 的任意排列，使其相对于 B 的优势最大化。
// 示例 1：
// 输入：A = [2,7,11,15], B = [1,10,4,11]
//输出：[2,11,7,15]
//
// 示例 2：
// 输入：A = [12,24,8,32], B = [13,25,32,11]
//输出：[24,32,8,12]
//
// 提示：
// 1 <= A.length = B.length <= 10000 
// 0 <= A[i] <= 10^9 
// 0 <= B[i] <= 10^9 
// 
// Related Topics 贪心 数组 排序 
// 👍 164 👎 0

public class LC870_优势洗牌 {
    public static void main(String[] args) {
        Solution solution = new LC870_优势洗牌().new Solution();
        int[] result = solution.advantageCount(new int[]{2, 7, 11, 15}, new int[]{1, 10, 4, 11});
        System.out.println("测试用例1的输出:" + Arrays.toString(result));
        result = solution.advantageCount(new int[]{12, 24, 8, 32}, new int[]{13, 25, 32, 11});
        System.out.println("测试用例2的输出:" + Arrays.toString(result));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] advantageCount(int[] nums1, int[] nums2) {
            //创建一个降序排序的队列
            PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o2[1] - o1[1];
                }
            });
            //向队列中添加nums2的元素，分别是下标和值
            for (int i = 0; i < nums2.length; i++) {
                queue.add(new int[]{i,nums2[i]});
            }
            //将nums1升序排序
            Arrays.sort(nums1);
            //left是nums1中最小的元素下标，right是最大的
            int left = 0,right = nums1.length - 1;
            //结果集
            int[] result = new int[nums1.length];
            //每次弹出队列中的最大的元素与nums1对战
            while(!queue.isEmpty()){
                int[] nums2_popup = queue.poll();//弹出队列头元素(头元素始终是队列中最大的)
                //nums1最大的打得过nums2最大的，就自己上
                if (nums1[right] > nums2_popup[1]){
                    result[nums2_popup[0]] = nums1[right--];
                }
                //打不过，就让nums最小的去送人头，不然浪费兵力
                else {
                    result[nums2_popup[0]] = nums1[left++];
                }
            }
            return result;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}